#include "myTree.h"
#include <iostream>


using namespace std;
TreeNode* Thrt = new TreeNode('#', NULL, NULL, Link, Thread); 
//树节点初始化
TreeNode::TreeNode(char data, TreeNode* leftChild, TreeNode* rghtChild, NodeTag lTag, NodeTag riTag){
    this->data = data;
    this->leftChild = leftChild;
    this->rightChild = rightChild;
    this->lTag = lTag;
    this->rTag = rTag;
}

//销毁树节点
TreeNode::~TreeNode(){
    if(lTag == Link&&this->leftChild!= nullptr)
        delete this->leftChild;
    if(rTag == Link&&this->rightChild!= nullptr)
        delete this->rightChild;
}

//打印树节点
void TreeNode::printNode()
{
    cout << this->data;
}

//初始化一颗空树
MyTree::MyTree(){
    this->root = NULL;
    this->isThread = false;
}

//前序构造树辅助函数
void MyTree::preOrderBuild(TreeNode*& root, const char data[], int& index){
    if(data[index] == '@'){
        root = NULL;
        index++;
    }
    else{
    root = new TreeNode(data[index], NULL, NULL, Link, Link);
    index++;
    preOrderBuild(root->leftChild, data, index);
    preOrderBuild(root->rightChild, data, index);
    }
}

//销毁树辅助函数
void MyTree::deleteTree(TreeNode*& root){
    if (root == NULL) {
    return; 
}
    if (root->lTag == Link) deleteTree(root->leftChild); 
    if (root->rTag == Link) deleteTree(root->rightChild); 
    root = NULL; 
    delete root; 
}
    
    
//初始化树
MyTree::MyTree(const char data[]){
    if(data[0]=='@') this->root = NULL;
    else{
        int index = 0; 
        preOrderBuild(this->root, data, index);
        this->isThread = false;
    }
}

//复制节点
TreeNode* MyTree::copyNode(TreeNode* node){
    if(node == NULL) return NULL;
    TreeNode* newNode = new TreeNode(node->data, NULL, NULL, node->lTag, node->rTag);
    newNode->leftChild = copyNode(node->leftChild);
    newNode->rightChild = copyNode(node->rightChild);
    return newNode;
}

//拷贝树
MyTree::MyTree(const MyTree& other){
    this->root = copyNode(other.root);
    this->isThread = other.isThread;
}

//销毁树
MyTree::~MyTree(){
    deleteTree(this->root);
}


//先序遍历二叉树并打印
void MyTree::preOrderTraverse() {
    stack<TreeNode*> s;
    TreeNode* p = this->root;
    while (p!= nullptr ||!s.empty()) {
        while (p!= nullptr) {
            p->printNode();
            if (p->rightChild!= nullptr) s.push(p->rightChild);
            p = p->leftChild;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
        }
    }
}

//中序遍历二叉树并打印
void MyTree::inOrderTraverse() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) { 
        inOrder(tmp);           
    } else {
        inOrderTraverse_Thr(Thrt);
    }
}

void MyTree::inOrder(TreeNode* node) {
    if (node) {
        inOrder(node->leftChild); 
        node->printNode();        
        inOrder(node->rightChild); 
    }
}

void MyTree::inOrderTraverse_Thr(TreeNode* node) {
    TreeNode* temp = node->leftChild; 
    while (temp != node) { 
        while (temp->lTag == Link) { 
            temp = temp->leftChild; 
        }
        temp->printNode();
        while (temp->rTag == Thread && temp->rightChild != node) { 
            temp = temp->rightChild; 
            temp->printNode();
        }
        temp = temp->rightChild;
    }
}

//后序遍历辅助函数
void MyTree::postOrderTraverseHelper(TreeNode* root){
    if(root!= nullptr){
        postOrderTraverseHelper(root->leftChild);
        postOrderTraverseHelper(root->rightChild);
        root->printNode();
    }   
}

//后序遍历二叉树并打印
void MyTree::postOrderTraverse() {
    postOrderTraverseHelper(this->root);
}

//定位二叉树中的节点
TreeNode& MyTree::locateNode(const char& d) {
    TreeNode* tmp = this->root; 
    return *locate(tmp, d); 
}

TreeNode* MyTree::locate(TreeNode* node, const char& c) {
    if (node->data == c) { 
        return node; 
    }
    if (node->leftChild && node->lTag != Thread) { 
        TreeNode* p = locate(node->leftChild, c); 
        if (p) {
            return p; 
        }
    }
    if (node->rightChild && node->rTag != Thread) { 
        TreeNode* p = locate(node->rightChild, c); 
        if (p) {
            return p; 
        }
    }
    return NULL; 
}

//数叶节点
int MyTree::countLeaf() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) { 
        return leafNum(tmp);      
    }
    return 0; 
}

int MyTree::leafNum(TreeNode* node) {
    if (!node) {
        return 0; 
    } else if(!node->leftChild && !node->rightChild) {
        return 1; 
    } else {
        return leafNum(node->leftChild) + leafNum(node->rightChild); 
    }
}

//数树高度
int MyTree::countHeight() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) { 
        return treeHeight(tmp);    
    }
    return 0; 
}

int MyTree::treeHeight(TreeNode* node) {
    if (!node) {
        return 0; 
    } else {
        int m = treeHeight(node->leftChild); 
        int n = treeHeight(node->rightChild); 
        return (m > n) ? m + 1 : n + 1; 
    }
}


//线索化二叉树
TreeNode* pre = NULL; 
bool MyTree::inOrderThreading() {
    this->isThread = true; 
    Thrt->rightChild = Thrt; 
    if (!this->root) { 
        Thrt->leftChild = Thrt; 
    } else {
        Thrt->leftChild = this->root; 
        pre = Thrt;
        inThreading(this->root);
        pre->rTag = Thread;
        pre->rightChild = Thrt; 
        Thrt->rightChild = pre;
    }
    return this->isThread; 
}

void MyTree::inThreading(TreeNode* node) {
    if (node != NULL) { 
        inThreading(node->leftChild); 
        if (node->leftChild == NULL) {
            node->lTag = Thread; 
            node->leftChild = pre; 
        }
        if (pre->rightChild == NULL) {
            pre->rTag = Thread; 
            pre->rightChild = node; 
        }
        pre = node;
        inThreading(node->rightChild);
    }
}

//判断是否是线索二叉树
bool MyTree::isThreadedTree() {
    return this->isThread; 
}

//寻找中序线索二叉树某节点的前驱节点
TreeNode& MyTree::preNode(const TreeNode& node) {
    TreeNode* p = node.leftChild; 
    if (this->isThread == false) { 
        this->inOrderThreading(); 
    }
    if (node.lTag == Thread) {
        return *(node.leftChild); 
    } else {
        return *(inOrderLastNode(p)); 
    }
}
//寻找中序线索二叉树某节点的后继节点
TreeNode& MyTree::nextNode(const TreeNode& node) {
    TreeNode* p = node.rightChild; 
    if (this->isThread == false) {
        this->inOrderThreading(); 
    }
    if (node.rTag == Thread) { 
        return *(node.rightChild); 
    } else {
        return *(inOrderFirstNode(p));
    }
}
//找中序最后一个节点
TreeNode* MyTree::inOrderLastNode(TreeNode* node) {
    TreeNode* tmp = node; 
    while (tmp->rTag == Link) { 
        tmp = tmp->rightChild; 
    }
    return tmp; 
}
//找中序第一个节点
TreeNode* MyTree::inOrderFirstNode(TreeNode* node) {
    TreeNode* tmp = node; 
    while (tmp->lTag == Link) {
        tmp = tmp->leftChild; 
    }
    return tmp; 
}



HuffmanNode::HuffmanNode(int v, int f) : value(v), freq(f), left(nullptr), right(nullptr) {}

bool Compare::operator()(HuffmanNode* a, HuffmanNode* b) {
    return a->freq > b->freq;
}

HuffmanTree::HuffmanTree(const int& n, const int vals[]) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (int i = 0; i < n; i++) {
        pq.push(new HuffmanNode(vals[i], vals[i])); 
    }
    while (pq.size() > 1) { 
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop(); 
        HuffmanNode* combined = new HuffmanNode(0, left->freq + right->freq);
        combined->left = left;
        combined->right = right; 
        pq.push(combined); 
    }
    root = pq.top(); 
}

HuffmanTree::~HuffmanTree() {
}

void HuffmanTree::generateCodes(HuffmanNode* node, string code, map<int, string>& codes) {
    if (!node) return; 
    if (!node->left && !node->right) {
        codes[node->value] = code; 
    }
    generateCodes(node->left, code + "0", codes); 
    generateCodes(node->right, code + "1", codes); 
}

void HuffmanTree::printHuffmanCodes() {
    map<int, string> codes;
    generateCodes(root, "", codes);
    vector<pair<int, string>> sortedCodes(codes.begin(), codes.end());
    sort(sortedCodes.begin(), sortedCodes.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
        return a.first > b.first; 
    });
    for (const auto& pair : sortedCodes) {
        cout << pair.first << ":" << pair.second << endl;
    }
}